<head>
    <meta charset="UTF-8">
<title>算法提高 小X的购物计划</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】<br />
小X打算去超市shopping。小X没什么钱，只有N元。超市里有M种物品，每种物品都需要money，在小X心中有一个重要度。有的物品有无限件，有的物品只有几件。小X想让他买的物品重要度之和最大，请问这个和最大是多少？<br />
【输入格式】</p>
<div>第一行为两个整数N，M。</div>
<div>以下M行，每行包含三个整数P，R，C，分别表示价格、重要度和个数。若C为-1则表示无限件。</div>
<p>【输出格式】<br />
输出只有一行，即题目中要求的最大和。<br />
【样例输入】</p>
<div>2 10</div>
<div>3 7 2</div>
<div>2 4 -1</div>
<p>【样例输出】<br />
22<br />
【数据规模和约定】</p>
<div>对于20%的数据，N&lt;=20，每种物品都只有一件。</div>
<div>对于50%的数据，N&lt;=100，没有无限件的物品。</div>
<div>对于100%的数据，N&lt;=1000，M&lt;=100。</div>